#include"Heap.h"
void HeapInit(Heap* php, HPDataType* a, int n)//堆的初始化
{
	assert(a);
	php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	memcpy(php->_a, a, sizeof(HPDataType) * n);
	php->_capcity = n;
	php->_size = n;
}
void AdJustUp(HPDataType* a, int n, int root)//向上排序算法
{
	int child = root;//孩子节点
	int parent = (child - 1) / 2;//父亲节点
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php,HPDataType x)//插入数据,是在最后插，插入之后也要保持堆的性质，所以需要向上排序算法
{
	assert(php);
	if (php->_capcity == php->_size)
	{
		php->_capcity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capcity);
		if (tmp == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
		else
		{
			php->_a = tmp;
			php->_a[php->_size++] = x;
			AdJustUp(php->_a, php->_size, php->_size - 1);
		}
	}
}
void HeapPop(Heap* php)//删除数据,是删除头元素，将头尾元素交换，删除尾元素，在进行一次向下排序
{
	assert(php);
	assert(php->_size > 0);
	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;
	AdJustDown(php->_a, php->_size, 0);
}
HPDataType HeapTop(Heap* php)//获取堆顶元素
{
	assert(php);
	return php->_a[0];
}
void HeapDestroy(Heap* php)//销毁堆
{
	assert(php);
	free(php->_a);
	php->_capcity=php->_size = 0;
}
void Swap(HPDataType* n1, HPDataType* n2)//交换两个元素
{
	HPDataType tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}
void AdJustDown(HPDataType* a, int n, int root)//向下调整算法
{
	//找到最小的孩子
	int parent = root;
	int child = 2 * parent + 1;//先把左孩子当作两个孩子中最小的
	while (child < n)
	{
		if (child+1<n&&a[child + 1] < a[child])//防止越界
		{
			child++;
		}
		else
		{
			if (a[child] < a[parent])
			{
				//父子节点交换
				Swap(&a[child], &a[parent]);
			}
			else
			{
				break;
			}
			parent = child;
			child = 2 * parent + 1;
		}
	}
}